#pragma once
#include <iostream>
#include <assert.h>
#include <vector>
#include <string>
using std::vector;
using std::string;
using std::pair;
using std::cout;
using std::endl;
using std::make_pair;

namespace xy {
	template<class K, class V, class HashFunc>
	class hashTable;
	
	template<class K, class V>
	struct hashNode {
		typedef hashNode<K, V> node;
		pair<K, V> _kv;
		node* _next;
	
		hashNode(const pair<K, V>& kv, node* next)
			:_kv(kv)
			, _next(next)
		{
		}
	};

	template<class K>
	struct DefHashFunc {
		size_t operator()(const K& k) {
			return k;
		}
	};

	template<>
	struct DefHashFunc<string> {
		size_t operator()(const string& k) {
			size_t hash = 0;
			for (auto it : k) {
				hash *= 9;
				hash += it;
			}
			return hash;
		}
	};
	
	template<class K, class Ref, class Ptr, class V, class HashFunc>
	struct hash_iterator {
		typedef hashNode<K, V> node;
		typedef hashTable<K, V, HashFunc> hash;
		typedef hash_iterator<K, Ref, Ptr, V, HashFunc> self;
		node* _node;
		hash* _hash;
	
		hash_iterator(node* n, hash* h)
			:_node(n)
			, _hash(h)
		{
		}
	
		self& operator++() {
			if (_node->_next) {
				_node = _node->_next;
				return *this;
			}
			else {
				HashFunc hf;
				size_t hashi = hf(_node->_kv.first) % _hash->_ht.size();
				hashi++;
				while (hashi < _hash->_ht.size()) {
					if (_hash->_ht[hashi]) {
						_node = _hash->_ht[hashi];
						return *this;
					}
					else {
						hashi++;
					}
				}
				_node = nullptr;
				return *this;
			}
		}

		Ref operator*() {
			return _node->_kv.first;
		}

		Ptr operator->() {
			return &(_node->_kv.first);
		}

		bool operator!=(const self& it) {
			return _node != it._node;
		}

		bool operator==(const self& it) {
			return _node == it._node;
		}
	};
	
	template<class K, class V, class HashFunc = DefHashFunc<K>>
	class hashTable {
		template<class K, class Ref, class Ptr, class V, class HashFunc>
		friend struct hash_iterator;
	public:
		typedef hash_iterator<K, K&, K*, V, HashFunc> iterator;
		typedef hashNode<K, V> node;
	
		hashTable(){
			_ht.resize(10, nullptr);
			_n = 0;
		}
	
		iterator begin() {
			for (int i = 0; i < _ht.size(); ++i) {
				if (_ht[i])
					return iterator(_ht[i], this);
			}
			return iterator(nullptr, this);
		}
	
		iterator end() {
			return iterator(nullptr, this);
		}

		iterator find(const K& k) {
			HashFunc hf;
			size_t i = hf(k) % _ht.size();
			node* cur = _ht[i];
			while (cur) {
				if (hf(cur->_kv.first) == hf(k)) {
					return iterator(cur, this);
				}
				else
					cur = cur->_next;
			}
			return iterator(nullptr, this);
		}
	
		bool insert(const pair<K, V>& kv) {
			HashFunc hf;
			if (find(kv.first) != end()) {
				return false;
			}

			if (_n == _ht.size()) {
				size_t newsize = _ht.size() * 2;
				vector<node*> newhash;
				_ht.resize(newsize);
				newhash.resize(newsize, nullptr);
	
				for (int i = 0; i < _ht.size(); ++i) {
					node* cur = _ht[i];
					while (cur) {
						node* next = cur->_next;
						
						size_t hashi = hf(cur->_kv.first) % newhash.size();
						cur->_next = newhash[hashi];
						newhash[hashi] = cur;
	
						cur = next;
					}
					_ht[i] = nullptr;
				}
				_ht.swap(newhash);
			}
	
			size_t hashi = hf(kv.first) % _ht.size();
			node* newnode = new node(kv, nullptr);
			newnode->_next = _ht[hashi];
			_ht[hashi] = newnode;
			++_n;
			return true;
		}

		bool erase(const K& k) {
			HashFunc hf;
			size_t i = hf(k) % _ht.size();
			node* cur = _ht[i];
			node* prev = nullptr;
			while (cur) {
				if (hf(cur->_kv.first) == hf(k)) {
					if (prev) {
						prev->_next = cur->_next;
						delete cur;
						return true;
					}
					else {
						_ht[i] = cur->_next;
						delete cur;
						return true;
					}
				}
				else
					prev = cur;
					cur = cur->_next;
			}
			return false;
		}

		void print() {
			for (int i = 0; i < _ht.size(); ++i) {
				printf("[%d]:", i);
				node* cur = _ht[i];
				while(cur){
					cout << cur->_kv.first << "/" << cur->_kv.second << ",";
					cur = cur->_next;
				}
				cout << endl;
			}
		}
	private:
		vector<node*> _ht;
		size_t _n;
	};
}